Άλγεβρα Boole
Άλγεβρα Boole Boolean Algebra, Άλγεβρα Μπουλ - Ένας Επιστημονικός Κλάδος της Άλγεβρας που οι μεταβλητές λαμβάνουν μόνον δύο τιμές π.χ. 0,1 Ετυμολογία Η ονομασία "άλγεβρα" σχετίζεται ετυμολογικά με την λέξη "[[]]". Ιστορία Ο μαθηματικός George Boole, 1815-1864) παρουσίασε το 1847 μια άλγεβρα με μεταβλητές δύο τιμών (που καλούνται "λογικές μεταβλητές"). Ουσιαστικά παρουσίασε με τα μαθηματικά της εποχής του την Αριστοτέλεια λογική του είναι ή δεν είναι. Σήμερα η άλγεβρα αυτή ονομάζεται άλγεβρα Boole, ή δυαδική άλγεβρα, ή διακοπτική άλγεβρα και έχει βρει ευρεία εφαρμογή στην σχεδίαση του λογισμικού και των κυκλωμάτων των Ηλεκτρονικών Υπολογιστών, επειδή είναι ιδανική για χειρισμό λογικών συναρτήσεων και πράξεων στο Δυαδικό Σύστημα. Ο παρακάτω ορισμός της άλγεβρας Μπουλ στηρίζεται σε συγκεκριμένα αξιώματα που παρουσίασε το 1933 ο μαθηματικός Edward Vermilye Huntington, 1874-1952). Αξιώματα του Huntington *'Αξίωμα Α1: Ισοδυναμία' Υπάρχει ένα σύνολο Κ με αντικείμενα ή στοιχεία, που υπακούουν σε μια σχέση ισοδυναμίας, α = β (όπου το σύμβολο ‘=’ διαβάζεται είναι ίσο με), που ικανοποιεί την αρχή της αντικατάστασης. Αν το στοιχείο α ανήκει στο σύνολο Κ, γράφουμε € Κ, (όπου το σύμβολο € διαβάζεται ανήκει στο). Γράφοντας α = β, εννοούμε ότι το α μπορεί να αντικατασταθεί από το β, σε οποιαδήποτε λογική έκφραση που περιέχει το α, χωρίς να επηρεαστεί η τιμή της έκφρασης αυτής. Ιδιότητες της σχέσης ισοδυναμίας είναι η ανακλαστική ιδιότητα (α = α), η συμμετρική ιδιότητα (α = β <=> β = α), (όπου το σύμβολο <=> διαβάζεται ταυτίζεται με το), και η μεταβατική ιδιότητα (α = β και β = γ => α = γ) , (όπου το σύμβολο => διαβάζεται συνεπάγεται). *'Αξίωμα Α2.1: Πράξη πρόσθεσης' Ένας κλειστός νόμος (σύμβολο ‘+’ διαβάζεται συν), που θα τον λέμε πρόσθεση, ορίζεται έτσι, ώστε αν α € Κ και β € Κ, τότε (α + β) € Κ. *'Αξίωμα Α2.2: Πράξη πολλαπλασιασμού' Ένας κλειστός νόμος (σύμβολο ‘•’ διαβάζεται επί), που θα τον λέμε πολλαπλασιασμό ορίζεται έτσι, ώστε αν α € Κ και β € Κ, τότε (α • β) € Κ. *'Αξίωμα Α3.1: Ουδέτερο στοιχείο πρόσθεσης' Υπάρχει μόνο ένα στοιχείο 0 € Κ τέτοιο, ώστε (για κάθε α € Κ) (α + 0) = α. Το 0 λέγεται ουδέτερο στοιχείο της πρόσθεσης. *'Αξίωμα Α3.2: Ουδέτερο στοιχείο πολλαπλασιασμού' Υπάρχει μόνο ένα στοιχείο 1 € Κ τέτοιο, ώστε (για κάθε α € Κ) (α • 1) = α. Το 1 λέγεται ουδέτερο στοιχείο του πολλαπλασιασμού. *'Αξίωμα Α4.1: Αντιμετάθεση προσθετέων' Η πρόσθεση είναι αντιμεταθετική, δηλαδή (α + β) = (β + α). *'Αξίωμα Α4.2: Αντιμετάθεση παραγόντων' Ο πολλαπλασιασμός είναι αντιμεταθετικός, δηλαδή (α • β) = (β • α). *'Αξίωμα Α5.1: Επιμεριστική πρόσθεση' Η πρόσθεση είναι επιμεριστική επί του πολλαπλασιασμού, δηλαδή α + (β • γ) = (α + β) • (α + γ). Αυτό είναι ένα αξίωμα της άλγεβρας Μπουλ που δεν ισχύει στην άλγεβρα των πραγματικών αριθμών! *'Αξίωμα Α5.2: Επιμεριστικός πολλαπλασιασμός' Ο πολλαπλασιασμός είναι επιμεριστικός επί της πρόσθεσης, δηλαδή α • (β + γ) = (α • β) + (α • γ). (Σημείωση : Όταν δεν υπάρχει περίπτωση παρανόησης, παραλείπουμε την αναγραφή του επί ‘•’ και χρησιμοποιούμε απλή παράθεση των παραγόντων. Για παράδειγμα, η σχέση εδώ μπορεί να γραφτεί έτσι : α (β + γ) = α β + α γ) . *'Αξίωμα Α6: Συμπληρώματα' Για κάθε στοιχείο α € Κ υπάρχει μόνο ένα στοιχείο α', για το οποίο ισχύει ότι α + α' = 1 (A6.1) και α • α' = 0 (A6.2) *'Αξίωμα Α7: Διάκριτα στοιχεία' Υπάρχουν τουλάχιστον δυο στοιχεία α και β μέσα στο Κ που δεν είναι ισοδύναμα. Ανάλογα με το πλήθος και το είδος των στοιχείων του Κ, καθορίζεται και μια άλγεβρα. Η απλούστερη άλγεβρα Μπουλ έχει μόνο δυο στοιχεία, δηλαδή το Κ = {0, 1}. Για τα στοιχεία αυτά ισχύουν τα εξής : 1' = 0 και 0' = 1, 0 + 0 = 0 και 1 • 1 = 1, 0 + 1 = 1 και 1 • 0 = 0, 1 + 0 = 1 και 0 • 1 = 0, 1 + 1 = 1 και 0 • 0 = 0 (Α7). Αρχή του Δυϊσμού Αν σε μια λογική έκφραση αντικατασταθούν * το (συν +) με (επί •) και * το (επί •) με (συν +) και * το (μηδέν 0) με (ένα 1) και * το (ένα 1) με (μηδέν 0) δημιουργείται η δυϊκή έκφραση, που ισχύει όπως και η αρχική. Η αρχή του δυϊσμού εμφανίζεται και στα αξιώματα του Huntington, που εμφανίζονται κατά ζεύγη. Συνολοθεωρία Η Συνολοθεωρία (set theory)είναι στην πραγματικότητα μια Άλγεβρα Boole. Ας δούμε τις αντιστοιχίες: * Τα ονόματα στοιχείων του Κ στην θεωρία συνόλων είναι ονόματα συνόλων. * Η πράξη πρόσθεση αντιστοιχεί στην ένωση συνόλων. * Η πράξη πολλαπλασιασμός αντιστοιχεί στην τομή συνόλων. * Το στοιχείο μηδέν αντιστοιχεί στο κενό σύνολο. * Το στοιχείο μονάδα αντιστοιχεί στο παγκόσμιο σύνολο C. (Όπως είναι γνωστό, δεν ορίζεται το σύνολο όλων των συνόλων). * Το συμπλήρωμα στοιχείου αντιστοιχεί στο συμπληρωματικό συνόλου ως προς το U. Με τις αντιστοιχίσεις αυτές, κάθε σχέση της άλγεβρας Boole μπορεί να μετατραπεί σε συνολοθεωρητική σχέση. Υπάρχει συγκριτικός πίνακας παρακάτω. Άλγεβρα Boole και Προτασιακή Λογική Η Προτασιακή Λογική (propositional calculus) είναι στην πραγματικότητα και αυτή μία Άλγεβρα Boole. Λογική πρόταση είναι κάθε σύνολο χαρακτήρων ή λέξεων που μπορούμε να του δώσουμε την τιμή «ψευδής» ή «αληθής». Η πρόταση p=κερδίσω το λαχείο μεθαύριο δεν είναι λογική πρόταση. Η πρόταση q=ακέραιος αριθμός 4 είναι άρτιος είναι λογική πρόταση και έχει αληθοτιμή = «αληθής». Θα μπορούσαμε να δούμε την προτασιακή λογική (πράξεις με λογικές προτάσεις) ως μια άλγεβρα Boole. Ας δούμε τις αντιστοιχίες: * Τα στοιχεία του Κ στην προτασιακή λογική είναι λογικές προτάσεις. * Η πρόσθεση αντιστοιχεί σε διάζευξη (Ή). * Ο πολλαπλασιασμός αντιστοιχεί σε σύζευξη (ΚΑΙ). * Το μηδέν αντιστοιχεί στο ψευδής. * Το ένα αντιστοιχεί στο αληθής. * Το συμπλήρωμα αντιστοιχεί στην άρνηση της πρότασης. Υποσημειώσεις Εσωτερική Αρθρογραφία * Λογική * Μαθηματικά * Άλγεβρα Βιβλιογραφία * Cori, Rene, and Lascar, Daniel, 2000. Mathematical Logic: A Course with Exercises. Oxford Univ. Press. Chpt. 2. *Dahn, B. I. (1998) “Robbins algebras are Boolean: A revision of McCune’s computer-generated solution of the Robbins problem,” Journal of Algebra 208: 526-32. *Paul Halmos, 1963. Lectures on Boolean Algebras. Van Nostrand. *Paul Halmos and Steven Givant, 1998. Logic as Algebra. Dolciani Mathematical Expositions No. 21, Mathematical Association of America. *Stoll, R. R., 1979 (1963). Set Theory and Logic. Dover. Ιστογραφία * Boolean Algebra from AllAboutCircuits * Boolean algebra, Simple English Wikipedia. * Stanford Encyclopedia of Philosophy: "The Mathematics of Boolean Algebra," by J. Donald Monk. A monograph available free online: * Burris, Stanley N.; Sankappanavar, H. P., 1981. A Course in Universal Algebra. Springer-Verlag. ISBN 3540905782. Category: Άλγεβρα Category: Μαθηματικά